use std::cmp::Ordering;
use std::{fmt, ops};

/// [Distinct powers](https://projecteuler.net/problem=29)
fn main() {
    for n in &[5u32, 100] {
        let mut list = vec![];
        for a in 2..=(*n) {
            for b in 2..=(*n) {
                list.push(exp(a as u128, b));
            }
        }
        list.sort();
        list.dedup();
        println!("{:4}: {}", n, list.len());
    }
}

#[derive(Eq)]
struct Bignum(u128, u128, u128, u128, u128, u128, u128, u128, u128, u128);
impl fmt::Display for Bignum {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "{:020}{:020}{:020}{:020}{:020}{:020}{:020}{:020}{:020}{:020}",
            self.9, self.8, self.7, self.6, self.5, self.4, self.3, self.2, self.1, self.0
        )
    }
}
impl ops::MulAssign<u128> for Bignum {
    fn mul_assign(&mut self, rhs: u128) {
        self.0 *= rhs;
        self.1 *= rhs;
        self.2 *= rhs;
        self.3 *= rhs;
        self.4 *= rhs;
        self.5 *= rhs;
        self.6 *= rhs;
        self.7 *= rhs;
        self.8 *= rhs;
        self.9 *= rhs;
        let max = 100u128.pow(10);
        if self.0 >= max {
            self.1 += self.0 / max;
            self.0 %= max;
        }
        if self.1 >= max {
            self.2 += self.1 / max;
            self.1 %= max;
        }
        if self.2 >= max {
            self.3 += self.2 / max;
            self.2 %= max;
        }
        if self.3 >= max {
            self.4 += self.3 / max;
            self.3 %= max;
        }
        if self.4 >= max {
            self.5 += self.4 / max;
            self.4 %= max;
        }
        if self.5 >= max {
            self.6 += self.5 / max;
            self.5 %= max;
        }
        if self.6 >= max {
            self.7 += self.6 / max;
            self.6 %= max;
        }
        if self.7 >= max {
            self.8 += self.7 / max;
            self.7 %= max;
        }
        if self.8 >= max {
            self.9 += self.8 / max;
            self.8 %= max;
        }
    }
}
impl Ord for Bignum {
    fn cmp(&self, other: &Self) -> Ordering {
        let mut ords = vec![];
        ords.push(self.9.cmp(&other.9));
        ords.push(self.8.cmp(&other.8));
        ords.push(self.7.cmp(&other.7));
        ords.push(self.6.cmp(&other.6));
        ords.push(self.5.cmp(&other.5));
        ords.push(self.4.cmp(&other.4));
        ords.push(self.3.cmp(&other.3));
        ords.push(self.2.cmp(&other.2));
        ords.push(self.1.cmp(&other.1));
        ords.push(self.0.cmp(&other.0));
        for iter in ords {
            match iter {
                Ordering::Equal => {}
                rst => return rst,
            }
        }
        Ordering::Equal
    }
}
impl PartialOrd for Bignum {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}
impl PartialEq for Bignum {
    fn eq(&self, other: &Self) -> bool {
        self.0 == other.0
            && self.1 == other.1
            && self.2 == other.2
            && self.3 == other.3
            && self.4 == other.4
            && self.5 == other.5
            && self.6 == other.6
            && self.7 == other.7
            && self.8 == other.8
            && self.9 == other.9
    }
}

fn exp(a: u128, b: u32) -> Bignum {
    let mut s = Bignum(1, 0, 0, 0, 0, 0, 0, 0, 0, 0);
    let mut b = b;
    while b > 0 {
        let n = {
            if b > 5 {
                5
            } else {
                b
            }
        };
        let m = a.pow(n);
        s *= m;
        b -= n;
    }
    s
}
